//
//  GraphMatrix_dfs.swift
//  SwiftyDSA
//
//  Created by Archer on 2018/8/16.
//  Copyright © 2018年 Archer. All rights reserved.
//

import Foundation

extension GraphMatrix {
    
    /// 深度优先搜索
    /// depth-first search
    public func dfs(startAt index: Int, clock: inout Int) {
        // 发现当前位于index的顶点
        vertexes[index].status = .discovered
        clock += 1
        vertexes[index].dTime = clock
        
        // 考察位于index处顶点的所有邻居
        var vertexIdx = firstNbr(at: index)
        while vertexIdx > -1 {

            switch vertexes[vertexIdx].status {
                // 若位于vertexIdx的顶点未被访问 则可以从这里扩展
            case .undiscovered:
                // 引入树的层次结构
                edges[index][vertexIdx]?.type = .tree
                vertexes[vertexIdx].parent = index
                // 继续扩展
                dfs(startAt: vertexIdx, clock: &clock)
                
                // 若位于vertexIdx的顶点已被发现但尚未被访问 那么它属于可以被后来顶点指向的祖先顶点
            case .discovered:
                edges[index][vertexIdx]?.type = .backword
                
                // 若位于vertexIdx的顶点已被访问 则视承袭关系分为前向边或跨边
            case .visited:
                edges[index][vertexIdx]?.type = dTime(at: index) < dTime(at: vertexIdx) ? .forword : .cross
            }
            
            // 转向下一个邻接顶点
            vertexIdx = nextNbr(at: index, relativeTo: vertexIdx)
        }
        // 位于index访问完毕
        vertexes[index].status = .visited
        clock += 1
        vertexes[index].fTime = clock
    }
}
